#ifndef CHEN_NODE_TREE
#define CHEN_NODE_TREE
#include <algorithm>
#include <iostream>
using namespace std;

/**
    普通的结点Node
    GetData();
    SetData();

 */
template <typename DT>
class Node
{
private:
    DT element;

public:
    Node(const DT & ele) 
    : element{ ele } { }

    Node(const DT && ele) 
    : element{ std::move( ele ) } { }

    ~Node() { }

    const DT & GetData() 
    {
        return element;
    }

    void SetData(const DT & newdata)
    {
        element = newdata;
    }


    
};

/**
 * 添加了左右子树的BinaryNode
    可以读到左右结点的Node
 */
template <typename DT>
class BinaryNode : public Node<DT>
{


private:
    BinaryNode *left;
    BinaryNode *right;
public:
    BinaryNode( const DT & ele, BinaryNode *lt, BinaryNode *rt )
        : Node<DT>::element{ ele }, left{ lt }, right{ rt } { }
        
    BinaryNode( DT && ele, BinaryNode *lt, BinaryNode *rt )
        : Node<DT>::element{ std::move( ele ) }, left{ lt }, right{ rt } { }


    ~BinaryNode() {  }


    BinaryNode* & GetLeft()
    {
        return left;
    }
    BinaryNode* & GetRight()
    {
        return right;
    }


};

/**
由于可以调节平衡，所以需要参数height
 */
template <typename DT>
class AvlNode : public BinaryNode<DT>
{
private:
    int height;
public:
    AvlNode(const DT & ele, AvlNode *lt, AvlNode *rt, int h = 0)
        : BinaryNode<DT>::element{ ele }, 
        BinaryNode<DT>::left{ lt }, 
        BinaryNode<DT>::right{ rt }, 
        height{ h } { }

    AvlNode(const DT && ele, AvlNode *lt, AvlNode *rt, int h = 0)
        : BinaryNode<DT>::element{ std::move(ele) }, 
        BinaryNode<DT>::left{ lt }, 
        BinaryNode<DT>::right{ rt }, 
        height{ h } { }

    ~AvlNode() {}

    int GetHeight() const
    {
        return height;
    }

    void 
};









/**
 * 
 */
template <typename DT>
class BianrySearchTree
{
public:
    BinarySearchTree( ) : root{nullptr} 
    {}


    /**
     * Copy constructor
     */
    BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
    {
        root = clone( rhs.root );
    }



    /**
     * Move constructor
     */
    BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
    {
        rhs.root = nullptr;
    }


      /**
     * Destructor for the tree
     */
    ~BinarySearchTree( )
    {
        makeEmpty( );
    }


     /**
     * Copy assignment
     */
    BinarySearchTree & operator=( const BinarySearchTree & rhs )
    {
        BinarySearchTree copy = rhs;
        std::swap( *this, copy );
        return *this;
    }
    
   


    
    virtual bool isEmpty() const
    {}

    virtual const DT &finMin() const
    {}

    virtual const DT &finMax() const
    {}

    virtual void printTree(ostream &out = cout) const
    {}

    virtual void makeEmpty()
    {}

    virtual void insert(const DT &x)
    {}

    virtual void insert(const DT &&x)
    {}

    virtual void remove(const DT &x)
    {}

    virtual void remove( DT &&x)
    {}

 


private:
    
    BinaryNode<DT> *root;

    void insert(const DT &x, BinaryNode<DT> *&t);
  
    void insert(DT &&x, BinaryNode<DT> *&t);

    void remove(const DT &x, BinaryNode<DT> *&t);

    bool contains(const DT &x, BinaryNode<DT> *t);

    void makeEmpty(BinaryNode<DT> *&t);
   
    void printTree(BinaryNode<DT> *t, ostream &out);
    
    BinaryNode<DT> *clone(BinaryNode<DT> *t) const;

    void insert(const DT &x, BinaryNode<DT> *&t);

    void insert(const DT &&x, BinaryNode<DT> *&t);

    BinaryNode<DT> *finMin(BinaryNode<DT> *t) const;

    BinaryNode<DT> *finMax(BinaryNode<DT> *t) const;
};





/**
 * 平衡树继承二叉搜索树
 */
template <typename DT>
class AvlTree : public: BianrySearchTree<DT>
{
public:
   

   AvlTree( ) : root{ nullptr }
        { }
    
        
        AvlTree( const AvlTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        
        AvlTree( AvlTree && rhs ) : root{ rhs.root }
        {
            rhs.root = nullptr;
        }
    
        
        ~AvlTree( )
        {
            makeEmpty( );
        }

      
        AvlTree & operator=( const AvlTree & rhs )
        {
            AvlTree copy = rhs;
            std::swap( *this, copy );
            return *this;
        }
        
        AvlTree & operator=( AvlTree && rhs )
        {
            std::swap( root, rhs.root );        
            return *this;
        }

        

        virtual const DT & findMin() const
        { }

        virtual const DT & findMax() const
        { }

        
        virtual bool isEmpty() const
        { }

        virtual void makeEmpty()
        { }

        virtual void printTree(ostream & out = cout)
        { }

        virtual void insert(const DT & x) 
        { }

        virtual void insert(DT && x)
        { }

        virtual void remove(const DT & x) 
        { }

        virtual void remove(DT && x)
        { } 

        

private:
    AvlNode<DT> *root;


    void insert(const DT &x, AvlNode<DT> *&t);
  
    void insert(DT &&x, AvlNode<DT> *&t);

    void remove(const DT &x, AvlNode<DT> *&t);

    bool contains(const DT &x, AvlNode<DT> *t);

    void makeEmpty(AvlNode<DT> *&t);
   
    void printTree(AvlNode<DT> *t, ostream &out);

    void insert(const DT &x, AvlNode<DT> *&t);

    void insert(const DT &&x, AvlNode<DT> *&t);

    AvlNode<DT> *finMin(AvlNode<DT> *t) const;

    AvlNode<DT> *finMax(AvlNode<DT> *t) const;

        



    void balance( AvlNode * & t )
    { }

    void rotateWithLeftChild( AvlNode * & k1 )
    { }


    void rotateWithRightChild( AvlNode * & k2 )
    { }

    
    void doubleWithLeftChild( AvlNode * & k3 )
    { }

    
    void doubleWithRightChild( AvlNode * & k4 )
    { }

    
    int height( AvlNode *t ) const
    { }
};


#endif
